#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int numWays(int n)
    {
        if (n == 0 || n == 1)
            return 1;

        if (n == 2)
            return 2;

        long long a = 1;
        long long b = 2;
        long long c = 0;

        for (int i = 3; i <= n; ++i)
        {
            c = ((a % 1000000007) + (b % 1000000007)) % 1000000007;
            a = b;
            b = c;
        }

        return c;
    }
};